Finite state automatons (FSAs) are known. A FSA is sometimes called a finite automaton (FA) or a finite state machine (FSM). Moreover, a FSA in which transitions have weights assigned thereto is called a weighted finite state automaton (WFSA).
A pattern recognition device is known that performs pattern recognition with respect to sequential data, such as speech recognition, handwritten character recognition, or optical character recognition. As an example, the pattern recognition device outputs the single most probable recognition result or outputs N number of recognition results from the best recognition result to the N-th best recognition result corresponding to sequential data that has been input.
Meanwhile, there are also times when a pattern recognition device outputs a lattice as the recognition result. A lattice is a weighted digraph assigned with labels (input symbols) and appearance positions of the labels (input symbols). Thus, it can be said that a lattice is an appearance-position-assigned WFSA. Herein, an appearance position indicates the position of the sequential data, which is input to the pattern recognition device, corresponding to a label (an input symbol).
A lattice in which words represent the input symbols is generally called a word lattice. A lattice in which phonemes represent the input symbols is generally called a phoneme lattice. A lattice in which states of a hidden Markov model (HMM) represent the input symbols is generally called an HMM state lattice.
For example, in a pattern recognition device that performs pattern recognition with respect to speech data, sometimes an HMM is used as the model. Such a pattern recognition device records the sequence of states of the HMM, which have been passed during the recognition operation, in the form of a lattice; and outputs the recognition result in the form of an HMM state lattice in which the states of the HMM represent the input symbols.
Meanwhile, there are times when a pattern recognition device outputs a word-assigned HMM state lattice, in which the words represent the input symbols and the pairs of weights and HMM states represent the weights, in an appearance-position-assigned WFSA. In such an appearance-position-assigned WFSA, there exists a plurality of paths in which the same input symbol is assigned at the same appearance position, and there exist a number of empty transitions (ε transitions). Thus, at the subsequent stage of a pattern recognition device that outputs such an appearance-position-assigned WFSA, it is necessary to dispose a conversion device that eliminates elimination of unnecessary paths by executing a process of removing empty transitions (ε transitions) and a determinization process.
However, in such an appearance-position-assigned WFSA, even if the paths have the same appearance positions and are assigned with the same input symbols, there are times when those paths have different source states in the HMM. For example, even if the paths are assigned with the same input symbols, when the input symbols have different pronunciations, the source states in the HMM are different. However, in the conventional conversion device, such a plurality of paths is merged into a single path.